package com.lft.sort09.bucket_sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 桶排序
 */
public class BucketSort {
	public static void main(String[] args) {
		int[] a = {2, 6, 9, 3, 5, 1, -9, 7, -3, -1, -6, 8, 0};
		System.out.println(Arrays.toString(bucketSort(a, 5)));
	}
	
	public static int[] bucketSort(int[] a, int bucketSize) {
		int length = a.length;
		int max = a[0];
		int min = a[0];
		// 找到数组中的最大值和最小值。
		for (int i = 0; i < length; i++) {
			if (a[i] > max) {
				max = a[i];
			} else if (a[i] < min) {
				min = a[i];
			}
		}
		// bucketSize 表示每个桶中存放数据的个数。bucketCount 是桶的个数。
		int bucketCount = (max - min) / bucketSize + 1;
		// 以集合形式创建桶
		List<List<Integer>> buckets = new ArrayList<>(bucketCount);
		// 循环遍历初始化每个桶
		for (int i = 0; i < bucketCount; i++) {
			buckets.add(new ArrayList<>());
		}
		for (int i = 0; i < length; i++) {
			// 确定数组中每个元素在桶中的索引位置。然后将当前元素添加到桶中。
			// (a[i] - min) / bucketSize 就是小数在前面，大数在后面。这样遍历原数组，将每个元素放到桶中。
			buckets.get((a[i] - min) / bucketSize).add(a[i]);
		}
		// 临时索引，用于往原数组中存放排序好的元素。下面没有赋值，上面就需要提交初始化。
		int tempIndex = 0;
		for (int i = 0; i < buckets.size(); i++) {
			// 以每个桶中的元素大小创建一个数组。
			Integer[] bucketArrays = new Integer[buckets.get(i).size()];
			// 将每个桶中的所有元素，转成数组的形式。
			bucketArrays = buckets.get(i).toArray(bucketArrays);
			// 对数组排序【实现方法众多。】
			Arrays.sort(bucketArrays);
			//
			for (int j = 0; j < bucketArrays.length; j++) {
				a[tempIndex++] = bucketArrays[j];
			}
		}
		return a;
	}
}
